
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1793. -- [Ioi2008]Fish 鱼
</title><center><h2>1793: [Ioi2008]Fish 鱼
</h2><span class=green>Time Limit: </span>30 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>19&nbsp;&nbsp;<span class=green>Solved: </span>11<br>[<a href='submitpage.php?id=1793'>Submit</a>][<a href='problemstatus.php?id=1793'>Status</a>][<a href='bbs.php?id=1793'>Discuss</a>]</center><h2>Description</h2><div class=content>据Scheherazade说，在很远的沙漠中有一个湖。湖中起初有N条鱼。选择最值钱的K种宝石，对F条鱼的每一条只喂给它一块宝石。注意，因为K可能小于F，两条或更多的鱼可能会吞下同一种宝石。
随着时间的流逝，有些鱼吃掉了别的鱼。一条鱼能够吃掉另一条鱼，当且仅当它的长度是被吃掉的鱼的两倍(A 能吃掉B 当且仅当LA >= 2 * LB)。没有规则说明一条鱼何时会吃掉另一条鱼。有的鱼可能会一条接一条地吃掉几条小鱼，而有的鱼可能不吃别的鱼，即使它们有能力吃。当一条鱼吃掉一条小鱼时，它的身长并不改变，但是小鱼腹中的宝石会完好无损地进到大鱼腹中。
据Scheherazade说，如果你能够找到那个湖，你会被准许捕捉一条鱼，并且得到鱼腹中的宝石。你很想试试运气，但是在出发前很想知道捉到一条鱼可能会有多少种不同的宝石组合。

任务
写一个程序，给定每条鱼的长度以及其最初吞食的宝石的种类，找出鱼腹中宝石不同组合的数量对给定整数M取模的值。组合由每种宝石的数量定义，与宝石的排列顺序无关。同一类宝石中任意两块是没有区别的。

限制
1 <= F <= 500,000		湖中最初鱼的数量
1 <= K <= F			宝石的种类
2 <=M <= 30,000	
1 <= LX <= 1,000,000,000	鱼X的长度

</div><h2>Input</h2><div class=content>你的程序需要从标准输入上读入下列数据：
&#8226;	
&#8226;	第一行是整数F, 即湖中最初鱼的数量。
&#8226;	第二行是整数K, 即宝石的种类数。
不同类型的宝石分别用从 1 到 K的整数表示。
&#8226;	第三行是整数M。
&#8226;	以后 F 行中的每一行用由一个空格分隔的两个整数描述一条鱼：按顺序分别是鱼的长度以及鱼腹中的宝石的类型。
注意: 在所有的测试用例中，K 种宝石中的每一种都会至少有一块。
 
</div><h2>Output</h2><div class=content>输出
你的程序需要在标准输出上输出一个介于0和M-1(包含)的整数，即宝石所有可能的不同组合数量模M，占一行。
注意，在问题求解中，数值 M 除了简化计算外没有其他的作用。
评分
有总计 70 分的测试用例，其中K 不超过 7,000。在这些测试用例中，有总计25 分的测试用例的 K 不超过 20。

反馈细节
在竞赛中, 你提交的程序将用一些正式的数据进行测试，并向你显示测试结果的概要。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
5<br />
3<br />
7<br />
2 2<br />
5 1<br />
8 3<br />
4 1<br />
2 3	<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>4<br />
<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p>有 11 种可能的组合，所以你需要输出4，也就是11 模 7。<br />
<br />
这些可能的组合是: [1] [1,2] [1,2,3] [1,2,3,3] [1,3] [1,3,3] [2] [2,3] [2,3,3] [3] 和 [3,3]。 <br />
(对每一种组合, 我们列出其所包含的宝石。 例如，[2,3,3] 包含一块2型宝石和两块3型宝石)<br />
这些组合可以由下述方式获得:<br />
&#8226;	[1]: 如果你在第二条鱼 (或第四条) 吃掉任何其它鱼之前捕捉到它。 <br />
&#8226;	[1,2]: 如果第二条鱼吃掉第一条鱼, 它就会有一块 1 型宝石(它在初始时刻吞下的) 和一块2型宝石 (从第一条鱼腹中得到的)。<br />
&#8226;	[1,2,3]: 一种可能的途径是: 第四条鱼吃掉第一条鱼，然后第三条鱼又吃掉它。如果你此时捉到了第三条鱼，那它腹中就会有这三种宝石一样一块。<br />
&#8226;	[1,2,3,3]: 第四条鱼吃掉第一条鱼，第三条鱼吃掉第四条鱼，第三条鱼吃掉第五条鱼，你捉到了第三条鱼。<br />
&#8226;	[1,3]: 第三条鱼吃掉第四条鱼，你捉到了第三条鱼。<br />
&#8226;	[1,3,3]: 第三条鱼吃掉第五条鱼，第三条鱼吃掉第四条鱼，你捉到了第三条鱼。<br />
&#8226;	[2]: 你捉到了第一条鱼。<br />
&#8226;	[2,3]: 第三条鱼吃掉第一条鱼，你捉到了第三条鱼。<br />
&#8226;	[2,3,3]: 第三条鱼吃掉第一条鱼，第三条鱼吃掉第五条鱼，你捉到了第三条鱼。<br />
&#8226;	[3]: 你捉到了第三条鱼。<br />
&#8226;	[3,3]: 第三条鱼吃掉第五条鱼，你捉到了第三条鱼。<br />
<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day1'>Day1</a></p></div><center>[<a href='submitpage.php?id=1793'>Submit</a>][<a href='problemstatus.php?id=1793'>Status</a>][<a href='bbs.php?id=1793'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
